/* UNIX V7 source code: see /COPYRIGHT or www.tuhs.org for details. */

#include <stdlib.h>
#include <unistd.h>
#include "dextern.h"
#include "prototype.h"

	/* variables used locally */

	/* lookahead computations */

int tbitset;			/* size of lookahead sets */
struct looksets lkst[LSETSIZE];
int nlset = 0;			/* next lookahead set index */
int nolook = 0;			/* flag to suppress lookahead computations */
struct looksets clset;		/* temporary storage for lookahead computations */

	/* working set computations */

struct wset wsets[WSETSIZE];
struct wset *cwp;

	/* state information */

int nstate = 0;			/* number of states */
struct item *pstate[NSTATES + 2];	/* pointers to the descriptions of the states */
int tystate[NSTATES];		/* contains type information about the states */
int indgo[NSTATES];		/* index to the stored goto table */
int tstates[NTERMS];		/* states generated by terminal gotos */
int ntstates[NNONTERM];		/* states generated by nonterminal gotos */
int mstates[NSTATES];		/* chain of overflows of term/nonterm generation lists  */

	/* storage for the actions in the parser */

int amem[ACTSIZE];		/* action table storage */
int *memp = amem;		/* next free action table position */

	/* other storage areas */

int temp1[TEMPSIZE];		/* temporary storage, indexed by terms + ntokens or states */
int lineno = 1;			/* current input line number */
int fatfl = 1;			/* if on, error is fatal */
int nerrors = 0;		/* number of errors */

	/* storage for information about the nonterminals */

int **pres[NNONTERM + 2];	/* vector of pointers to productions yielding each nonterminal */
struct looksets *pfirst[NNONTERM + 2];	/* vector of pointers to first sets for each nonterminal */
int pempty[NNONTERM + 1];	/* vector of nonterminals nontrivially deriving e */

int main(int argc, char *argv[])
{

	setup(argc, argv);	/* initialize and read productions */
	tbitset = NWORDS(ntokens);
	cpres();		/* make table of which productions yield a given nonterminal */
	cempty();		/* make a table of which nonterminals can match the empty string */
	cpfir();		/* make a table of firsts of nonterminals */
	stagen();		/* generate the states */
	output();		/* write the states and the tables */
	go2out();
	hideprod();
	summary();
	callopt();
	others();
	exit(0);
}

void others(void)
{				/* put out other arrays, copy the parsers */
	int c, i, j;

	finput = fopen(PARSER, "r");
	if (finput == NULL)
		error("cannot find parser %s", PARSER);

	warray("yyr1", levprd, nprod);

	aryfil(temp1, nprod, 0);
	PLOOP(1, i) temp1[i] = prdptr[i + 1] - prdptr[i] - 2;
	warray("yyr2", temp1, nprod);

	aryfil(temp1, nstate, -1000);
	TLOOP(i) {
		for (j = tstates[i]; j != 0; j = mstates[j]) {
			temp1[j] = tokset[i].value;
		}
	}
	NTLOOP(i) {
		for (j = ntstates[i]; j != 0; j = mstates[j]) {
			temp1[j] = -i;
		}
	}
	warray("yychk", temp1, nstate);

	warray("yydef", defact, nstate);

	/* copy parser text */

	while ((c = getc(finput)) != EOF) {
		if (c == '$') {
			if ((c = getc(finput)) != 'A')
				putc('$', ftable);
			else {	/* copy actions */
				faction = fopen(ACTNAME, "r");
				if (faction == NULL)
					error("cannot reopen action tempfile");
				while ((c = getc(faction)) != EOF)
					putc(c, ftable);
				fclose(faction);
				ZAPFILE(ACTNAME);
				c = getc(finput);
			}
		}
		putc(c, ftable);
	}

	fclose(ftable);
}

char *chcopy(char *p, char *q)
{
	/* copies string q into p, returning next free char ptr */
	while ((*p = *q++) != 0)
		++p;
	return (p);
}

#define ISIZE 400
char *writem(int *pp)
{				/* creates output string for item pointed to by pp */
	int i, *p;
	static char sarr[ISIZE];
	char *q;

	for (p = pp; *p > 0; ++p);
	p = prdptr[-*p];
	q = chcopy(sarr, nontrst[*p - NTBASE].name);
	q = chcopy(q, " : ");

	for (;;) {
		*q++ = ++p == pp ? '_' : ' ';
		*q = '\0';
		if ((i = *p) <= 0)
			break;
		q = chcopy(q, symnam(i));
		if (q > &sarr[ISIZE - 30])
			error("item too big");
	}

	if ((i = *pp) < 0) {	/* an item calling for a reduction */
		q = chcopy(q, "    (");
		sprintf(q, "%d)", -i);
	}

	return (sarr);
}

char *symnam(int i)
{				/* return a pointer to the name of symbol i */
	char *cp;

	cp = (i >= NTBASE) ? nontrst[i - NTBASE].name : tokset[i].name;
	if (*cp == ' ')
		++cp;
	return (cp);
}

struct wset *zzcwp = wsets;
int zzgoent = 0;
int zzgobest = 0;
int zzacent = 0;
int zzexcp = 0;
int zzclose = 0;
int zzsrconf = 0;
int *zzmemsz = mem0;
int zzrrconf = 0;

void summary(void)
{				/* output the summary on the tty */

	if (foutput != NULL) {
		fprintf(foutput, "\n%d/%d terminals, %d/%d nonterminals\n", ntokens, NTERMS, nnonter, NNONTERM);
		fprintf(foutput, "%d/%d grammar rules, %d/%d states\n", nprod, NPROD, nstate, NSTATES);
		fprintf(foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n", zzsrconf, zzrrconf);
		fprintf(foutput, "%d/%d working sets used\n", (int)(zzcwp - wsets), WSETSIZE);
		fprintf(foutput, "memory: states,etc. %d/%d, parser %d/%d\n", (int)(zzmemsz - mem0), MEMSIZE, (int)(memp - amem), ACTSIZE);
		fprintf(foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE);
		fprintf(foutput, "%d extra closures\n", zzclose - 2 * nstate);
		fprintf(foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp);
		fprintf(foutput, "%d goto entries\n", zzgoent);
		fprintf(foutput, "%d entries saved by goto default\n", zzgobest);
	}
	if (zzsrconf != 0 || zzrrconf != 0) {
		fprintf(stdout, "\nconflicts: ");
		if (zzsrconf)
			fprintf(stdout, "%d shift/reduce", zzsrconf);
		if (zzsrconf && zzrrconf)
			fprintf(stdout, ", ");
		if (zzrrconf)
			fprintf(stdout, "%d reduce/reduce", zzrrconf);
		fprintf(stdout, "\n");
	}

	fclose(ftemp);
	if (fdefine != NULL)
		fclose(fdefine);
}

/* VARARGS1 */

void error(char *s, ...)
{				/* write out error comment */

	++nerrors;
	fprintf(stderr, "\n fatal error: ");
/*FIXME VARARG*/ fprintf(stderr, s);
	fprintf(stderr, ", line %d\n", lineno);
	if (!fatfl)
		return;
	summary();
	exit(1);
}

void aryfil(int *v, int n, int c)
{				/* set elements 0 through n-1 to c */
	int i;
	for (i = 0; i < n; ++i)
		v[i] = c;
}

int setunion(int *a, int *b)
{
	/* set a to the union of a and b */
	/* return 1 if b is not a subset of a, 0 otherwise */
	int i, x, sub;

	sub = 0;
	SETLOOP(i) {
		*a = (x = *a) | *b++;
		if (*a++ != x)
			sub = 1;
	}
	return (sub);
}

void prlook(struct looksets *p)
{
	int j, *pp;
	pp = p->lset;
	if (pp == 0)
		fprintf(foutput, "\tNULL");
	else {
		fprintf(foutput, " { ");
		TLOOP(j) {
			if (BIT(pp, j))
				fprintf(foutput, "%s ", symnam(j));
		}
		fprintf(foutput, "}");
	}
}

void cpres(void)
{				/* compute an array with the beginnings of  productions yielding given nonterminals
				   The array pres points to these lists */
	/* the array pyield has the lists: the total size is only NPROD+1 */
	int **pmem;
	int c, j, i;
	static int *pyield[NPROD];

	pmem = pyield;

	NTLOOP(i) {
		c = i + NTBASE;
		pres[i] = pmem;
		fatfl = 0;	/* make undefined  symbols  nonfatal */
		PLOOP(0, j) {
			if (*prdptr[j] == c)
				*pmem++ = prdptr[j] + 1;
		}
		if (pres[i] == pmem) {
			error("nonterminal %s not defined!", nontrst[i].name);
		}
	}
	pres[i] = pmem;
	fatfl = 1;
	if (nerrors) {
		summary();
		exit(1);
	}
	if (pmem != &pyield[nprod])
		error("internal Yacc error: pyield %d", pmem - &pyield[nprod]);
}

int indebug = 0;

void cpfir(void)
{
	/* compute an array with the first of nonterminals */
	int *p, **s, i, **t, ch, changes;

	zzcwp = &wsets[nnonter];
	NTLOOP(i) {
		aryfil(wsets[i].ws.lset, tbitset, 0);
		t = pres[i + 1];
		for (s = pres[i]; s < t; ++s) {	/* initially fill the sets */
			for (p = *s; (ch = *p) > 0; ++p) {
				if (ch < NTBASE) {
					SETBIT(wsets[i].ws.lset, ch);
					break;
				} else if (!pempty[ch - NTBASE])
					break;
			}
		}
	}

	/* now, reflect transitivity */

	changes = 1;
	while (changes) {
		changes = 0;
		NTLOOP(i) {
			t = pres[i + 1];
			for (s = pres[i]; s < t; ++s) {
				for (p = *s; (ch = (*p - NTBASE)) >= 0; ++p) {
					changes |= setunion(wsets[i].ws.lset, wsets[ch].ws.lset);
					if (!pempty[ch])
						break;
				}
			}
		}
	}

	NTLOOP(i) pfirst[i] = flset(&wsets[i].ws);
	if (!indebug)
		return;
	if ((foutput != NULL)) {
		NTLOOP(i) {
			fprintf(foutput, "\n%s: ", nontrst[i].name);
			prlook(pfirst[i]);
			fprintf(foutput, " %d\n", pempty[i]);
		}
	}
}

int state(int c)
{				/* sorts last state,and sees if it equals earlier ones. returns state number */
	int size1, size2;
	int i;
	struct item *p1, *p2, *k, *l, *q1, *q2;
	p1 = pstate[nstate];
	p2 = pstate[nstate + 1];
	if (p1 == p2)
		return (0);	/* null state */
	/* sort the items */
	for (k = p2 - 1; k > p1; k--) {	/* make k the biggest */
		for (l = k - 1; l >= p1; --l)
			if (l->pitem > k->pitem) {
				int *s;
				struct looksets *ss;
				s = k->pitem;
				k->pitem = l->pitem;
				l->pitem = s;
				ss = k->look;
				k->look = l->look;
				l->look = ss;
			}
	}
	size1 = p2 - p1;	/* size of state */

	for (i = (c >= NTBASE) ? ntstates[c - NTBASE] : tstates[c]; i != 0; i = mstates[i]) {
		/* get ith state */
		q1 = pstate[i];
		q2 = pstate[i + 1];
		size2 = q2 - q1;
		if (size1 != size2)
			continue;
		k = p1;
		for (l = q1; l < q2; l++) {
			if (l->pitem != k->pitem)
				break;
			++k;
		}
		if (l != q2)
			continue;
		/* found it */
		pstate[nstate + 1] = pstate[nstate];	/* delete last state */
		/* fix up lookaheads */
		if (nolook)
			return (i);
		for (l = q1, k = p1; l < q2; ++l, ++k) {
			int s;
			SETLOOP(s) clset.lset[s] = l->look->lset[s];
			if (setunion(clset.lset, k->look->lset)) {
				tystate[i] = MUSTDO;
				/* register the new set */
				l->look = flset(&clset);
			}
		}
		return (i);
	}
	/* state is new */
	if (nolook)
		error("yacc state/nolook error");
	pstate[nstate + 2] = p2;
	if (nstate + 1 >= NSTATES)
		error("too many states");
	if (c >= NTBASE) {
		mstates[nstate] = ntstates[c - NTBASE];
		ntstates[c - NTBASE] = nstate;
	} else {
		mstates[nstate] = tstates[c];
		tstates[c] = nstate;
	}
	tystate[nstate] = MUSTDO;
	return (nstate++);
}

int pidebug = 0;		/* debugging flag for putitem */

void putitem(int *ptr, struct looksets *lptr)
{
	struct item *j;

	if (pidebug && (foutput != NULL)) {
		fprintf(foutput, "putitem(%s), state %d\n", writem(ptr), nstate);
	}
	j = pstate[nstate + 1];
	j->pitem = ptr;
	if (!nolook)
		j->look = flset(lptr);
	pstate[nstate + 1] = ++j;
	if ((int *) j > zzmemsz) {
		zzmemsz = (int *) j;
		if (zzmemsz >= &mem0[MEMSIZE])
			error("out of state space");
	}
}

void cempty(void)
{				/* mark nonterminals which derive the empty string */
	/* also, look for nonterminals which don't derive any token strings */

#define EMPTY 1
#define WHOKNOWS 0
#define OK 1

	int i, *p;

	/* first, use the array pempty to detect productions that can never be reduced */
	/* set pempty to WHONOWS */
	aryfil(pempty, nnonter + 1, WHOKNOWS);

	/* now, look at productions, marking nonterminals which derive something */

      more:
	PLOOP(0, i) {
		if (pempty[*prdptr[i] - NTBASE])
			continue;
		for (p = prdptr[i] + 1; *p >= 0; ++p) {
			if (*p >= NTBASE && pempty[*p - NTBASE] == WHOKNOWS)
				break;
		}
		if (*p < 0) {	/* production can be derived */
			pempty[*prdptr[i] - NTBASE] = OK;
			goto more;
		}
	}

	/* now, look at the nonterminals, to see if they are all OK */

	NTLOOP(i) {
		/* the added production rises or falls as the start symbol ... */
		if (i == 0)
			continue;
		if (pempty[i] != OK) {
			fatfl = 0;
			error("nonterminal %s never derives any token string", nontrst[i].name);
		}
	}

	if (nerrors) {
		summary();
		exit(1);
	}

	/* now, compute the pempty array, to see which nonterminals derive the empty string */

	/* set pempty to WHOKNOWS */

	aryfil(pempty, nnonter + 1, WHOKNOWS);

	/* loop as long as we keep finding empty nonterminals */

      again:
	PLOOP(1, i) {
		if (pempty[*prdptr[i] - NTBASE] == WHOKNOWS) {	/* not known to be empty */
			for (p = prdptr[i] + 1; *p >= NTBASE && pempty[*p - NTBASE] == EMPTY; ++p);
			if (*p < 0) {	/* we have a nontrivially empty nonterminal */
				pempty[*prdptr[i] - NTBASE] = EMPTY;
				goto again;	/* got one ... try for another */
			}
		}
	}

}

int gsdebug = 0;

void stagen(void)
{
/* generate the states */

	int i, j;
	int c;
	struct wset *p, *q;

	/* initialize */

	nstate = 0;
	/* THIS IS FUNNY from the standpoint of portability */
	/* it represents the magic moment when the mem0 array, which has */
	/* been holding the productions, starts to hold item pointers, of a */
	/* different type... */
	/* someday, alloc should be used to allocate all this stuff... for now, we */
	/* accept that if pointers don't fit in integers, there is a problem... */

	pstate[0] = pstate[1] = (struct item *) mem;
	aryfil(clset.lset, tbitset, 0);
	putitem(prdptr[0] + 1, &clset);
	tystate[0] = MUSTDO;
	nstate = 1;
	pstate[2] = pstate[1];

	aryfil(amem, ACTSIZE, 0);

	/* now, the main state generation loop */

      more:
	SLOOP(i) {
		if (tystate[i] != MUSTDO)
			continue;
		tystate[i] = DONE;
		aryfil(temp1, nnonter + 1, 0);
		/* take state i, close it, and do gotos */
		closure(i);
		WSLOOP(wsets, p) {	/* generate goto's */
			if (p->flag)
				continue;
			p->flag = 1;
			c = *(p->pitem);
			if (c <= 1) {
				if (pstate[i + 1] - pstate[i] <= p - wsets)
					tystate[i] = MUSTLOOKAHEAD;
				continue;
			}
			/* do a goto on c */
			WSLOOP(p, q) {
				if (c == *(q->pitem)) {	/* this item contributes to the goto */
					putitem(q->pitem + 1, &q->ws);
					q->flag = 1;
				}
			}
			if (c < NTBASE) {
				state(c);	/* register new state */
			} else {
				temp1[c - NTBASE] = state(c);
			}
		}
		if (gsdebug && (foutput != NULL)) {
			fprintf(foutput, "%d: ", i);
			NTLOOP(j) {
				if (temp1[j])
					fprintf(foutput, "%s %d, ", nontrst[j].name, temp1[j]);
			}
			fprintf(foutput, "\n");
		}
		indgo[i] = apack(&temp1[1], nnonter - 1) - 1;
		goto more;	/* we have done one goto; do some more */
	}
	/* no more to do... stop */
}

int cldebug = 0;		/* debugging flag for closure */

void closure(int i)
{				/* generate the closure of state i */

	int c, ch, work, k;
	struct wset *u, *v;
	int *pi;
	int **s, **t;
	struct item *q;
	struct item *p;

	++zzclose;

	/* first, copy kernel of state i to wsets */

	cwp = wsets;
	ITMLOOP(i, p, q) {
		cwp->pitem = p->pitem;
		cwp->flag = 1;	/* this item must get closed */
		SETLOOP(k) cwp->ws.lset[k] = p->look->lset[k];
		WSBUMP(cwp);
	}

	/* now, go through the loop, closing each item */

	work = 1;
	while (work) {
		work = 0;
		WSLOOP(wsets, u) {

			if (u->flag == 0)
				continue;
			c = *(u->pitem);	/* dot is before c */

			if (c < NTBASE) {
				u->flag = 0;
				continue;	/* only interesting case is where . is before nonterminal */
			}

			/* compute the lookahead */
			aryfil(clset.lset, tbitset, 0);

			/* find items involving c */

			WSLOOP(u, v) {
				if (v->flag == 1 && *(pi = v->pitem) == c) {
					v->flag = 0;
					if (nolook)
						continue;
					while ((ch = *++pi) > 0) {
						if (ch < NTBASE) {	/* terminal symbol */
							SETBIT(clset.lset, ch);
							break;
						}
						/* nonterminal symbol */
						setunion(clset.lset, pfirst[ch - NTBASE]->lset);
						if (!pempty[ch - NTBASE])
							break;
					}
					if (ch <= 0)
						setunion(clset.lset, v->ws.lset);
				}
			}

			/*  now loop over productions derived from c */

			c -= NTBASE;	/* c is now nonterminal number */

			t = pres[c + 1];
			for (s = pres[c]; s < t; ++s) {
				/* put these items into the closure */
				WSLOOP(wsets, v) {	/* is the item there */
					if (v->pitem == *s) {	/* yes, it is there */
						if (nolook)
							goto nexts;
						if (setunion(v->ws.lset, clset.lset))
							v->flag = work = 1;
						goto nexts;
					}
				}

				/*  not there; make a new entry */
				if (cwp - wsets + 1 >= WSETSIZE)
					error("working set overflow");
				cwp->pitem = *s;
				cwp->flag = 1;
				if (!nolook) {
					work = 1;
					SETLOOP(k) cwp->ws.lset[k] = clset.lset[k];
				}
				WSBUMP(cwp);

			      nexts:;
			}

		}
	}

	/* have computed closure; flags are reset; return */

	if (cwp > zzcwp)
		zzcwp = cwp;
	if (cldebug && (foutput != NULL)) {
		fprintf(foutput, "\nState %d, nolook = %d\n", i, nolook);
		WSLOOP(wsets, u) {
			if (u->flag)
				fprintf(foutput, "flag set!\n");
			u->flag = 0;
			fprintf(foutput, "\t%s", writem(u->pitem));
			prlook(&u->ws);
			fprintf(foutput, "\n");
		}
	}
}

struct looksets *flset(struct looksets *p)
{
	/* decide if the lookahead set pointed to by p is known */
	/* return pointer to a perminent location for the set */

	struct looksets *q;
	int j, *w;
	int *u, *v;

	for (q = &lkst[nlset]; q-- > lkst;) {
		u = p->lset;
		v = q->lset;
		w = &v[tbitset];
		while (v < w)
			if (*u++ != *v++)
				goto more;
		/* we have matched */
		return (q);
	      more:;
	}
	/* add a new one */
	q = &lkst[nlset++];
	if (nlset >= LSETSIZE)
		error("too many lookahead sets");
	SETLOOP(j) {
		q->lset[j] = p->lset[j];
	}
	return (q);
}
